package com.wxweven.algorithm.array.bsearch;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author wxweven
 */
public class 有序数组大于等于某数的第一个元素 {
    /*
     * 举例 [2, 3, 5, 8, 9], 第一个大于等于6的数是8
     * 举例 [2, 3, 5, 8, 9], 第一个大于等于5的数是5
     */

    public int find(int[] arrs, int target) {
        if (arrs == null || arrs.length == 0) {
            return -1;
        }

        int res = -1;
        int left = 0;
        int right = arrs.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (arrs[mid] >= target) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return res;
    }

    public int find2(int[] arrs, int target) {
        if (arrs == null || arrs.length == 0) {
            return -1;
        }

        int res = -1;
        int left = 0;
        int right = arrs.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (arrs[mid] == target) {
                return mid;
            } else if (arrs[mid] < target) {
                left = mid + 1;
            } else if (target < arrs[mid]) {
                res = mid;
                right = mid - 1;
            }
        }

        return res;
    }

    @Test
    public void test() {
        int[] arrs = new int[]{2, 3, 5, 8, 9};
        int index1 = find(arrs, 6);
        Assert.assertEquals(3, index1);

        int index2 = find(arrs, 5);
        Assert.assertEquals(2, index2);
    }

    @Test
    public void test2() {
        int[] arrs = new int[]{2, 3, 5, 8, 9};
        int index1 = find2(arrs, 6);
        Assert.assertEquals(3, index1);

        int index2 = find2(arrs, 5);
        Assert.assertEquals(2, index2);
    }

}